package main

import "fmt"

/**
广度优先算法
解决两类问题
1、从节点A出发，有前往节点B的路径吗？
2、从节点A出发，前往节点B的哪条路径最短？

比如我有事要找到某个不认识的人叫xxx，此时
我的朋友有小王，小张，小李
小王的朋友有小明、小朱、小李
小张的朋友有小陈、小刘、小朱
小明的朋友有xxx
小朱的朋友有小范、小吴
小陈没有朋友
小刘没有朋友
小范的朋友有XXX
小吴没有朋友
此时我要通过朋友及朋友的朋友的关系网找到XXX
思路：把所有待搜索朋友的人放入队列，比如先把我放入队列，从队列中拿出我，找我的朋友中有没有人叫xxx，
如果有则结束；如果没有则把我的朋友们放入队列中，然后重复上面的步骤。
找到第一个就返回说明存在了，而且找到的是最短的路径
 */
func main()  {
	graph := make(map[string][]string,10)
	graph["我"] = []string{"小王","小张","小李"}
	graph["小王"] = []string{"小朱","小李","小明"}
	graph["小张"] = []string{"小陈","小刘","小朱"}
	graph["小朱"] = []string{"小范","小吴"}
	graph["小明"] = []string{"xxx"}
	graph["小陈"] = []string{}
	graph["小刘"] = []string{}
	graph["小范"] = []string{"xxx"}
	graph["小吴"] = []string{}

	//目标
	dest := "xxx"
	breadthFirst(graph,dest)
}

/**

 */
func breadthFirst(graph map[string][]string,dest string) {
	//可以用队列
	ch := make(chan string,10)
	ch <- "我"

	//找过了的数组
	searched := make([]string,0)
	for  {
		select {
		case name:=<-ch:

			//已经找过了就不要再找了
			if isContain(searched,name){
				fmt.Println(name+"已经找过了")
				break
			}
			searched = append(searched, name)
			//找到了
			if graph[name]!=nil && isContain(graph[name],dest){
				fmt.Println("找到"+dest+"了，是"+name+"的朋友")
				return
			}else{
				//没找到把这个人的朋友继续放入chan
				for _,name:=range graph[name]{
					ch<-name
				}
			}
		default:
		}
	}
}

/**
数据是否包含某元素
 */
func isContain(friends []string, dest string) bool {
	for _,name:=range friends{
		if name==dest{
			return true
		}
	}
	return false
}
